/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-10-20
 * Time: 23:34
 */
public class Solution {
    public boolean isMatch(String s, String p) {
        int row = p.length();
        int col = s.length();
        boolean[][] dp = new boolean[row+1][col+1];
        dp[0][0] = true;
        // dp[0][j] j > 0 为 false
        int index = 1;
        // p 需要前面连续为 * 才能保证匹配 dp[i][0]
        while (index <= row && p.charAt(index-1) == '*') {
            dp[index][0] = true;
            index++;
        }

        for (int i = 1; i <= row; i++) {
            char c = p.charAt(i-1);
            for (int j = 1; j <= col; j++) {
                char o = s.charAt(j-1);
                if (c == o || c == '?') {
                    // 两个字符相等
                    dp[i][j] = dp[i-1][j-1];
                } else if (c == '*') {
//                     * 可以匹配 0 个, 1 个, 2 个, 3 个 ...
//                     匹配 0 个时为 dp[i-1][j]
//                          1 个为  dp[i-1][j-1]
//                          2 个为  dp[i-1][j-2]
//                          ...
//                     dp[i][j] = dp[i-1][j] || dp[i-1][j-1] || dp[i-1][j-2] || dp[i-1][j-3] ...
//                     但是 将上式中 的 j 换为  j-1
//                     dp[i][j-1] = dp[i-1][j-1] || dp[i-1][j-2] || dp[i-1][j-3] ...
//                     所以
//                     dp[i][j] = dp[i-1][j] || dp[i][j-1]
                    dp[i][j] = dp[i-1][j] || dp[i][j-1];
                }
            }
        }
        return dp[row][col];
    }
}
